package newcoder.JZ12;

import java.util.HashSet;
import java.util.Set;

//请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长
//度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子
public class Solution {

    private char[] wordChar;

    private boolean contain = false;

    private boolean running = true;

    private int cross;

    private int height;

    public boolean hasPath(char[][] matrix, String word) {
        // write code here
        this.wordChar = word.toCharArray();
        int length = word.length();
        this.cross = matrix[0].length;
        this.height = matrix.length;

        out:
        for (int x = 0; x < height; x++) {
            for (int y = 0; y < cross; y++) {
                if (!running) {
                    break out;
                }
                Set<String> set = new HashSet<>();
                char[] chars = new char[length];
                back(chars, 0, matrix, x, y, set);
            }
        }
        return contain;
    }

    private void back(char[] temp, int index, char[][] matrix, int x, int y, Set<String> set) {
        if (!running) {
            return;
        }
        if (set.contains(x + "," + y)) {
            return;
        }
        if (x < 0 || x >= height || y < 0 || y >= cross) {
            return;
        }
        temp[index] = matrix[x][y];
        if (temp[index] != wordChar[index]) {
            return;
        }
        if (index == temp.length - 1) {
            contain = true;
            running = false;
            return;
        }

        String point = x + "," + y;
        set.add(point);
        back(temp, index + 1, matrix, x + 1, y, set);
        back(temp, index + 1, matrix, x, y + 1, set);
        back(temp, index + 1, matrix, x - 1, y, set);
        back(temp, index + 1, matrix, x, y - 1, set);
        set.remove(point);
    }

    public static void main(String[] args) {

        char[][] matrix = {{'a', 'b', 'c', 'e'}, {'s', 'f', 'c', 's'}, {'a', 'd', 'e', 'e'}};
        Solution solution = new Solution();
        boolean abcced = solution.hasPath(matrix, "see");
        System.out.println(abcced);
    }
}
